package 分类.回溯;

import java.util.HashMap;

public class 目标和 {
    public static int findTargetSumWays(int[] nums, int target) {
       if(nums.length==0) return 0;
       return dp(nums,target,0);
    }
    static HashMap<String, Integer> memo=new HashMap<>();
    static int dp(int[] nums,int res,int start){
        if(start==nums.length){
            if(res==0){
                return 1;
            }
            return 0;
        }
        String key=start+","+res;
        if(memo.containsKey(key)){
            return memo.get(key);
        }
        int result=dp(nums,res-nums[start],start+1)+dp(nums,res+nums[start],start+1);
        memo.put(key,result);
        return result;

    }

    public static void main(String[] args) {
        int[] nums={1,1,1,1,1};
        int target=3;
        System.out.println("findTargetSumWays(nums,target) = " + findTargetSumWays(nums, target));
    }
}
